﻿#ifndef __QUICKSORT__
#define __QUICKSORT__
#include "SortTool.h"
#include <stack>
#define RECURSION 1
#define BINARY 1
//快速排序 O(nlgn)，最坏情况是二次方
//性能取决于所选取的基准项.能将序列从中间划分，最为理想
//可以改进的地方：
//1.一般来讲，可以选取三个元素取中间数作为基准项（第一个，最后一个，以及中间的），来保证运行效率
//2.对于划分出来的较小序列（长度5-25）可以采取先忽略，然后再调用插入排序来综合解决
template <class item>
int partition(item arr[], int left, int right){
	int i = left-1, j = right;
	item key = arr[right];
	for(;;){
		//有人已经证明，当遇到与key 相等的元素时，两个指针都直接++，效率会高一些。
		//一个极端的例子是：arr 中全部都相等。
		while(arr[++i] <= key) if(i == right) break;
		while(arr[--j] >= key) if(j == left) break;
		if(i >= j) break;
		exchange(arr[i], arr[j]);
	}
	//if(i != right)//非必须判断：避免做原地交换
	exchange(arr[i] , arr[right]);
	return i;
}

#if RECURSION

#if BINARY
//快速排序的二进制版本，实质上是一种基数排序
//在划分的过程中，实际上进行了退化：对于大部分高位来讲，基本山没有用到
//因此每次划分后，会有对特殊情况的判断：i 自加到right 的情况
template <class item>
void quicksort_binary(item arr[], int left, int right, int digit){
	int i = left, j = right;
	if(arr == NULL || right <= left || digit >= BITSWORD) return;
	while(i != j){
		while(getbit(arr[i], digit) == 0 && i <j) ++i;
		while(getbit(arr[j], digit) == 1 && j >i) --j;
		exchange(arr[i], arr[j]);
	}
	if(getbit(arr[right], digit) == 0) ++i;//判断特殊性情况：该位上，每个待排序的数都是0，则将
	quicksort_binary(arr, left, i-1, digit+1);
	quicksort_binary(arr, i, right, digit+1);
}

template <class item>
void quicksort(item arr[], int left, int right){
	quicksort_binary(arr, left, right, 0);
}

#else
template <class item>
void quicksort(item arr[], int left, int right){
	if(arr == NULL || left >= right) return;
	int index = partition(arr, left, right);
	quicksort(arr, left, index-1);
	quicksort(arr, index+1, right);
}
#endif

#else
void stack_push(std::stack<int>& stack, int left, int right){
	stack.push(right); stack.push(left);
}
template <class item>
void quicksort(item arr[], int left, int right){
	if(arr == NULL || left >= right) return;
	std::stack<int> stack;
	stack_push(stack, left, right);
	for(;;){
		if(stack.empty()) break;
		int l = stack.top(); stack.pop();
		int r = stack.top(); stack.pop();
		if(l >= r) continue;
		int index = partition(arr, l, r);
		//先将大的文件放入栈中，虽不会影响排序的速度，但能保证栈的大小不会超过lgN
		if((index -l)>(r- index)){
			stack_push(stack, l, index-1); stack_push(stack, index+1, r);
		}
		else{
			stack_push(stack, index+1, r); stack_push(stack, l, index-1);
		}
	}
}
#endif
#endif